home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / simula / books / books.lha / kirkerud / binsearchtest.sim < prev    next >
Text File  |  1993-08-16  |  2KB  |  58 lines
  1. begin
  2.     
  3.   procedure Binary_search_in_table(table, low_bound, high_bound,  
  4.                                search_value, value_found, index_of_value);  
  5.       name value_found, index_of_value;  
  6.       integer array table;  
  7.       integer low_bound, high_bound, search_value, index_of_value;
  8.       Boolean value_found;
  9.     if low_bound > high_bound or
  10.        search_value < table(low_bound) or
  11.        search_value > table(high_bound)
  12.     then value_found := false else
  13.     begin integer middle;
  14.       while low_bound + 1 < high_bound do
  15.         begin
  16.             ! At this place it is always the case that
  17.             ! table(low_bound) <= search_value <= table(high_bound);
  18.           middle := (low_bound + high_bound)//2;
  19.           if table(middle) <= search_value
  20.             then low_bound  := middle 
  21.             else high_bound := middle;
  22.         end;
  23.         ! At this place it is always the case that
  24.         ! 1: table(low_bound) <= search_value <= table(high_bound);
  25.         ! 2: Either: low_bound + 1 = high_bound;
  26.         !        or: low_bound     = high_bound;
  27.       if search_value = table(high_bound) then
  28.         begin value_found := true; index_of_value := high_bound end else
  29.       if search_value = table(low_bound) then
  30.         begin value_found := true; index_of_value := low_bound end
  31.       else value_found := false;
  32.     end of Binary_search_in_table;
  33.  
  34.   integer array a(1:1000);
  35.   
  36.   integer ind;
  37.   
  38.   procedure bintest(val); integer val;
  39.     begin 
  40.       Boolean found; integer index;
  41.       Binary_search_in_table(a, 1, 1000, val, found, index);
  42.       outtext("The value "); outint(val, 0);
  43.       if found then begin outtext(" was found at index "); outint(index, 0) end
  44.       else outtext(" was not found");
  45.       outimage;
  46.     end;
  47.   
  48.   for ind := 1 step 1 until 1000 do a(ind) := 10*ind;
  49.   
  50.   bintest(100);
  51.   bintest(1000);
  52.   bintest(10);
  53.   bintest(10000);
  54.   bintest(10010);
  55.   bintest(0);
  56.   
  57. end
  58.